The present invention relates to an interlock variable acquisition system and method for permitting exclusive access to a shared resource by each of a plurality of processors over a common bus and which limits traffic on the common bus associated with the provision of such exclusive access.
Processing systems may include a plurality of processors which require access to a shared memory over a common bus in order to execute instructions in accordance with their respective programs. Such processors can be called upon to execute related program portions wherein the related program portions require that they be executed individually and not simultaneously with the execution of any other of the related program portions. Such related program portions are known as critical sections. Critical sections are required to provide a processor exclusive access to a shared resource, such as a shared memory and to thus assure that only one processor is executing a critical section at any one time.
Hence, in a shared memory multiprocessor system, provision must be made to allow a processor to have exclusive access to some shared resource during the time in which it is executing a critical section. When a processor is executing a critical section, no other processor can be in a related critical section. A critical section must be guarded so that only one processor can be in a critical section at any one time. The guard may be a code segment that precedes a critical section and which has the function to prevent more than one processor from executing a critical section.
One prior art method for implementing the guard into a critical section uses interlock variables. An interlock variable may have one of two values, an available value indicating that no processor is executing a critical section, and a busy value indicating that a processor is executing a critical section. In accordance with this method, the shared memory includes a memory location for storing the value of the interlock variable and each processor includes a register. When a processor wishes to enter a critical section, it reads the interlock variable within the memory location of the shared memory and loads that value of the interlock variable into its register. The processor also writes back to the interlock variable memory location of the shared memory the busy value of the interlock variable. The reading and writing of the interlock variable are performed atomically so that no other processor can access the common bus between the read and the write. If, following the read and the write, the register of the processor contains a busy value, the processor will not enter its critical section but instead perform the read and write operation again. However, if the register of the processor contains the available value of the interlock variable, the processor will enter its critical section.
The foregoing forms a loop in which the interlock variable in the interlock variable memory location of the shared memory is being tested. Such a loop is a type of guard known as a spin-lock. A busy value of the interlock variable indicates to the testing processor that another processor "owns" the interlock variable and is in a critical section. An available value of the interlock variable indicates that no processor is in its critical section. This processor acquires the interlock variable by writing the busy value into the interlock variable to communicate to all the processors that it is in its critical section. The processor then enters its critical section and no other processor wishing to enter a critical section will be able to do so until the processor in its critical section has completed its critical section.
When an owning processor completes execution of its critical section, it then communicates this fact to the other processors by writing the available value to the interlock variable in the shared memory. The next processor wishing to enter a critical section will then test the available value of the interlock variable and perform the same operations to enter its critical section. Ownership transfer of the interlock variable thus occurs when one processor writes the available value into the interlock variable and another processor subsequently acquires it in the manner described above.
While this method simplifies the implementation of assuring exclusive access to a critical section, the common bus becomes a performance bottleneck. This results because a processor wishing to acquire the interlock variable and enter a critical section must continually utilize the common bus to test the value of the interlock variable in the shared memory.
Another and still more efficient method of providing exclusive access to a critical section by a processor employs a cache associated with each of the processors for storing, locally to each processor, the most recent value of the interlock variable. Such caches can allow the value of the interlock variable to be modified relative to the shared memory. When the cache of another processor attempts to read the value of the interlock variable from the shared memory, the cache with the most recently modified value of the interlock variable intervenes and supplies the value of the interlock variable instead of the shared memory. In this way, all of the caches see the same correct value of the interlock variable even though the caches may be more up-to-date than the shared memory.
In such a system, when a processor desires to enter a critical section, its cache fetches the value of the interlock variable from either memory or the cache having the most recently updated value of the interlock variable, stores it, and then sends that value to its associated processor. If the interlock variable has a busy value, the cache does not follow the read with a write. Subsequent testing of the value of the interlock variable by this processor is performed locally in its cache, and, as a result, the shared bus is not accessed for this purpose. All processors wishing to enter a critical section obtain the busy value of the interlock variable in its associated cache and go into a loop, with each processor testing its local copy.
Eventually, the owning processor releases the interlock variable by executing a write instruction for writing the available value of the interlock variable on the shared bus while a "LOCK pin" is asserted. Each cache with a copy of the interlock variable invalidates its copy upon seeing the locked write. The next time such a processor wishes to enter a critical section, its cache will obtain, over the common bus, the available value of the interlock variable from either the shared memory or a cache, will become the owner of the interlock variable, and locally set the value of the interlock variable in its cache to the busy value. Thus, processors that subsequently read the interlock variable will read a busy value.
Hence, in accordance with the above-described prior art method, the common bus is used more efficiently by allowing each processor to cache the value of the interlock variable locally within its cache and to locally test the value of the interlock variable without using the common bus except for initially loading the interlock variable into its cache. Considerable common bus traffic still occurs, however, after a processor completes a critical section and writes the available value to the interlock variable. This is because all processors invalidate their copies of the value of the interlock variable when the owning processor releases the interlock. Each processor must then in turn obtain the new value of the interlock variable by the common bus, making the common bus a bottleneck in the process. With this method, the number of common bus accesses each time ownership transfer of the interlock occurs is proportional to the number of processors waiting to enter a critical section. This level of common bus activity is still too high for processing systems having a large number of processors. Hence, there is a need in the art for an improved interlock variable acquisition system and method to permit exclusive access to critical sections by each of a plurality of processors which further limits the traffic on a common bus associated with the provision of such exclusive access.